#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INT_SIZE 100
#define LIST_INCREATMENT 10

typedef int Status;
typedef int ElemType;

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *Linklist;

Status init_node(LNode *p) // 对节点初始化
{
    p->next = NULL;
    p->data = 0;
    return OK;
}

Status insert_node(LNode *head, ElemType data) // 尾插法
{
    LNode *p = (LNode *)malloc(sizeof(LNode));
    while (head->next != NULL) // 不断往后查找,直到最后一个节点(head->next 的写法虽然正确但是在这个函数里再想拿到头节点就难了,所以可以使用一个指针p代替head->next循环)
    {
        head = head->next;
    }
    head->next = p; // 链接最后节点与新节点
    init_node(p);
    p->data = data;
    return OK;
}

Status show_node(LNode *head) // 按顺序展示节点的值
{
    while (head->next) // head->next 的写法虽然正确但是在这个函数里再想拿到头节点就难了,所以可以使用一个指针p代替head->next循环
    {//优化的写法看57行
        head = head->next;
        printf("%d ", head->data);
    }
    printf("\n");
}
// 算法2.8
Status getElem_L(LNode *head, int i, ElemType *e) // 查找第i个数,存在返回OK并且使用e记录,否则返回ERROR
{
    LNode *p = head->next;
    int j = 1;                       // 控制位置
    while (p->next != NULL && j < i) // 往后查找
    {
        p = p->next;
        j++;
    }
    if (j == i) // 如果第i个位置存在,使用e存储
    {
        *e = p->data;
    }
    else // 不存在这个位置,返回ERROR
    {
        return ERROR;
    }
    return OK;
}

// 算法2.9
Status ListInsert_L(LNode *head, int i, ElemType e) // 在第i个元素之前插入,使得插入节点位置为i
{
    LNode *p = (LNode *)malloc(sizeof(LNode)); // 分配一个空间用来存储e并插入链表
    init_node(p);

    LNode *q = head;         // q用来索引,指向插入节点的前一个节点
    p->data = e;             // 给插入节点赋值
    int j = 1;               // 记录第几个节点数
    while (q->next && j < i) // 在第i的前一个位置停下
    {
        q = q->next;
        j++;
    }
    if (!q->next) // 如果插入位置不正确
    {
        return ERROR;
    }
    else // 插入位置正确
    {
        p->next = q->next; // 链接p与后面的节点
        q->next = p;       // 把前面的节点与p链接
    }
    return OK;
}

// 算法2.10(改写的)
Status Delete_L(LNode *L, int i, ElemType *e) // 删除第i个元素,返回其值
{
    LNode *p = L->next;
    int j = 1; // 记录位置
    while (j < i - 1 && p->next != NULL)
    {
        p = p->next;
        j++;
    }
    if (p->next == NULL)
    {
        return ERROR;
    }
    LNode *q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return OK;
}

// 算法2.11
Status head_insert(LNode *L, ElemType e) // 头插法
{
    LNode *p = (LNode *)malloc(sizeof(LNode));
    init_node(p);
    p->data = e;       // 对插入的新节点赋值
    p->next = L->next; // 插入第一个位置
    L->next = p;
    return OK;
}

// 算法2.12
Status Merge_Llist(LNode *La, LNode *Lb) // 合并排序
{
    // 这个修改了链表la,lb。实在觉得课本写的很迷lc不知道有什么用
    /*
    我对这个算法的理解就是,pa,pb负责分别指向La,Lb剩余的元素,已经插入的元素不再记录
    而lc相当于一个针,以La为头，重新编制La,将pa和pb指向的元素不断的缝起来直到pa或者pb到头了
    之后拼接没到头的(pa或pb)即可实现La的覆写。
    */
    LNode *pa = La->next;
    LNode *pb = Lb->next;
    LNode *pc = La;
    // while的写法很巧妙,节约了空间
    while (pa && pb) // 如果都没到头
    {
        if (pa->data <= pb->data) // 选择小的那个数
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    // 合并剩余链
    pc->next = pa ? pa : pb; // pa和pb有一个是空的,将pc的next指针指向pa或pb中不为空的那个节点;
    /*此双目运算符用法
    表达式1 ? 表达式2 : 表达式3
    如果表达式1为真，则整个表达式的值为表达式2的值，否则为表达式3的值
    */
    free(Lb); // free了Lb,Lb的下面的节点没释放啊?应该会内存泄漏吧
    return OK;
}

int main()
{
    LNode *head = (LNode *)malloc(sizeof(LNode));
    init_node(head);
    // 尾插法
    for (int i = 1; i < 10; ++i)
    {
        insert_node(head, i);
    }
    // 展示链表
    show_node(head);
    ElemType *e = (ElemType *)malloc(sizeof(ElemType)); // 用于获取第i个数的值
    *e = -1;
    // 获取链表的第i个值
    getElem_L(head, 3, e);
    printf("\n第三个值为:%d\n", *e); // 如果存在输出这个值,否则输出-1
    // 第i个节点前插入
    ListInsert_L(head, 4, 33); // 在第四个节点处插入一个数3
    show_node(head);
    // 删除操作
    Delete_L(head, 4, e); // 删除刚刚插入的33
    printf("\n删除的值为:%d\n", *e);
    show_node(head);
    // 头插法插入
    head_insert(head, 0);  // 头插法,插入一个0
    head_insert(head, -1); // 头插法,插入一个-1
    printf("头插法插入后:\n");
    show_node(head);
    // 归并排序
    LNode *head2 = (LNode *)malloc(sizeof(LNode));
    init_node(head2); // 只malloc不初始化相当于买房子不给房产证,流氓行为
    for (int i = -2; i < 10; i += 2)
    {
        insert_node(head2, i);
    }
    show_node(head2); // show第二个链表
    printf("进行合并:\n");
    Merge_Llist(head, head2); // 合并
    show_node(head);
}
